Using Java or C#
Monitor for concurrency kernel
implies defensive multithreading programming
1. Introduction : read the associated paper which contains two families
of examples
2. Process synchronization example: symmetrical rendez-vous paradigm.
the chameneos paradigm
The synchronization example is the
mutating chameneos paradigm [Kaiser 2003]. It involves a symmetrical
rendez-vous before peer-to-peer cooperation of concurrent processes.
The cooperation, depicted as a possible colour mutation between the
chameneos of a pair, is not developed in this paper. Here we cope only
with a solution where a chameneos eager to cooperate calls a
rendez-vous server in order to find a partner.
3. Resource allocation example.
3.1. A new solution for a
well known
paradigm, the dining philosophers
The dining philosophers, originally posed by Dijkstra
[Dijkstra 7I], is a paradigm for concurrent resource allocation. Five
philosophers spend their life alternately thinking and eating. To dine,
each philosopher sits around a circular table at a fixed place. In
front of each philosopher is a plate of food, and between each pair of
philosophers is a chopstick. In order to eat, a philosopher needs two
chopsticks, and they agree that each will use only the chopsticks
immediately to the left and to the right of his place. The problem is
to write a program simulating the philosopher’s behaviours and to
devise a protocol that avoids two unfortunate conclusions. In the first
one, all philosophers are hungry but none is able to acquire both
chopsticks since each holds one chopstick and refuses to give it up.
This is deadlock, a safety concern. In the second one, a hungry
philosopher will always lack one of the two chopsticks which are
alternately used by its neighbours. This is starvation, a liveness
consideration.
This paradigm has two well known approaches for obtaining a solution.
In the first one, the chopsticks are allocated one by one, and a
reliable solution is obtained by adding one of the usual constraints
for deadlock prevention: the chopsticks are allocated in fixed (e.g.,
increasing) order; a chopstick allocation is denied as soon as the
requested allocation would lead to an unsafe state (seated dinner, with
only 4 chairs). Ada implementation of this approach can be found [Burns
1995, Barkaoui 1997]. In the second one, the chopsticks are allocated
globally only, which is a safe solution; when a fair solution is
necessary, it is obtained by adding reservation constraints, care being
taken that these constraints do not reintroduce deadlock. Ada
implementation are given in [Brosgol 1996, Kaiser 1997]
Let us consider now another approach which does not seem to have been
much experimented except in [Kaiser 1997]. The chopsticks are allocated
as many as available and the allocation is completed as soon as the
missing chopsticks are released. Let us observe the behaviour of this
solution when implemented in Java and in Ada and from these
experiments, let us determine the conditions of its correctness.
3.2. Several
implementations
are provided and compared
The
implemented solutions are:
- a.
an
Ada simulation
of the
Java deadlock prone implementation (Java monitor semantics simulation)
- b.
an
Ada simulation
of the
Java deadlock free implementation (Java
monitor semantics simulation)
- c.
an
Ada simulation
of the
Java deadlock free and fair implementation (Java
monitor semantics simulation)
- d. an Ada deadlock
free and fair
implementation with a
single waiting queue (using
Ada monitor semantics)
- e.
an
Ada simulation
of
the Java notification objects implementation (Java monitor semantics
simulation)
- f.
an
Ada simulation
of the
Java condition and lock implementation (Java monitor semantics
simulation)
- g. an Ada
deadlock free, fair and deterministic implementation (using
Ada monitor semantics with entry families and requeue )
- h. an Ada simulation of Java global
allocation of Chops (Java
monitor semantics simulation)
- h1. an Ada global allocation of Chops (using
Ada monitor semantics with entry families)
The original solutions and the measured data are
given in the full paper below
3.3. The Resource example implementations have been analysed by Quasar,
our validation
tool
The data collected by Quasar are:
- the number of places of the
generated coloured Petri net,
- the number of transitions of the
generated coloured Petri net,
- the number of places and
transitions due to the chop package with the protected object
- the number of nodes of the
generated reachability graph
- the number of arcs of the
generated reachability graph
The analysed implementations are:
a_UCHOP JAVA ADA (program and Quasar report)
b_RCHOP JAVA ADA (program and Quasar report)
c_RFCHOP JAVA ADA (program and Quasar report)
d_RCHOP ADA SINGLE (program and Quasar report)
e_NOTIFICATION JAVA ADA (program and Quasar
report)
f_CONDITIONS JAVA ADA (program and Quasar report)
g_RCHOP ADA FAMILIES (program and Quasar report)
h_RCHOP JAVA GLOBAL (program and Quasar report)
i_PROGRAM SKELETON (program and Quasar report)
3.4. The implementations have been simulated in Ada and
instrumented
The different implementations have been instrumented for measuring
concurrency effectiveness and collecting data:
- PairRatio: ratio of times a
philosopher starts eating while another is already eating,
- SingletonsRatio: ratio of times
a philosopher starts eating alone,
- NbStructuralRefusals: number of
denials due to a neighbour already eating,
- NbCautiousRefusals: number of
denials due to deadlock or starvation prevention,
- Simulation time: duration of the
simulation run,
- Allocation time: mean allocation
time for a philosopher during the simulation,
- Allocation ratio: ratio of
time used allocating the chopsticks.
The original solutions have been
modified for allowing these measurements.
Several packages have been added :
- protected_machine,
allowing shared random generators
- monitoring,
allowing simulation data collection
The full program is present in
1_CHOPCODE MONITORS and is composed
of:
chop.adb which is a dummy code
which must be replaced by the experimented one stored in another
folder
chop.ads
diner.adb which is the main program
global.adb
global.ads
monitoring.adb which contains the number of runs (MaxStrokes) and the
individual messages (here replaced by null statement in procedure
Message)
monitoring.ads
protected_machine.adb
protected_machine.ads
The main program is diner.adb
Once compiled (with GNAT for example), just run ./diner
The simulated implementations of the package chop.adb
are in the following folders:
1_CHOPCODE MONITORS (programs
skeleton)
b_RCHOP JAVA ADA
c_RFCHOP JAVA ADA
d_RCHOP ADA SINGLE
e_NOTIFICATION JAVA ADA
f_CONDITIONS JAVA ADA
g_RCHOP ADA FAMILIES
h_GLOBAL JAVA ADA
4. The full paper
Using Java or C#
Monitor for concurrency kernel
implies defensive multithreading programming
authors: Claude Kaiser, Jean-François
Pradat-Peyre, Sami Évangelista, Pierre Rousseau
CEDRIC - CNAM Paris
292, rue St Martin, 75003 Paris
{kaiser, peyre, evangeli, rousseau}[at]cnam[dot]fr
http://quasar.cnam.fr/
It contains the data
collected by Quasar and the data recorded by the simulations.
Last update: March 29, 2006